This invention relates to a Galois field linear transformer and more particularly to such a Galois field linear transformer which achieves multiple cycle transformations in a single cycle.
Conventional arithmetic logic circuits used for error correction and detection, communications, encoding and decoding and general bit manipulation using Galois field linear transformations may be implemented in hardware or software. Hardware implementations are expensive, require significant chip space and energy and are not generally programmable. Software implementations avoid some of these disadvantages but have their own shortcomings. For example software implementation can require many instructions per bit for processing. Thus for an implementation requiring four instructions (cycles) per bit a sixteen bit input would consume 64 cycles of machine time. More realistically in a typical software implementation which processes 6 million bits per second using four or five instructions (cycles) per bit 24-30 million instructions or cycles are needed. When as is often the case more than one circuit is used, four or five, then the cycles required increase to 120 to 150 million. And this is doubled for systems using both a transmitter and receiver. This is a substantial portion of the capacity of conventional processors.
It is therefore an object of this invention to provide an improved Galois field linear transformer for e.g., bit manipulation, error correction and detection, communications, encoding and decoding, encryption and decryption, scrambling and descrambling and cyclical redundancy checking using polynomials.
It is a further object of this invention to provide such an improved Galois field linear transformer which accomplishes multiple cycle Galois field linear transformations in a single cycle.
The invention results from the realization that a fast, effective, economical, Galois field linear transformer for accomplishing multi-bit, multi-cycle transformation in a single cycle can be achieved with a matrix including a plurality of cells, each cell including an exclusive OR gate, an AND gate having an output connected to the exclusive OR gate and a programmable storage device for providing an input to its associated AND gate for setting the matrix to obtain a multi-cycle Galois field linear transformation in a single cycle.
This invention features a Galois field linear transformer including a matrix responsive to a number of input bits in one or more bit streams and having a plurality of outputs for providing the Galois field linear transformation of those bits. The matrix includes a plurality of cells each cell including an exclusive OR logic circuit and AND logic circuit having an output connected to the exclusive OR logic circuit and an input connected to one of the input bits and a programmable storage device providing an input to its associated AND logic circuit for setting the matrix to obtain a multi-cycle Galois field linear transformation of the inputs in a single cycle.
In a preferred embodiment each exclusive OR logic circuit may have its output connected to the input of the next successive exclusive OR logic circuit except for the last exclusive OR logic circuit whose output is connected to the output of the matrix and the first exclusive OR logic circuit whose input is connected to a zero level. The programmable storage device may include a number of storage units each one programmed for enabling a different Galois field linear transformation. The inputs to the matrix may include state inputs representative of previous state conditions of the Galois field linear outputs for the matrix the state inputs may be fed back from the previous state conditions represented by the Galois field linear outputs of the matrix.